package union_find_Algorithm;

/**
 * 根节点权重法优化并查集
 */
@SuppressWarnings("all")
public class UnionFind_weight {
    private int maxsize;
    private int[] root;
    private int[] rank; // 存放每个节点的高度

    public UnionFind_weight(int maxsize) {
        this.maxsize = maxsize;
        root = new int[this.maxsize];
        rank = new int[this.maxsize];
        for (int i = 0; i < this.maxsize; i++) {
            root[i] = i;
            rank[i] = 1; // 初始的节点高度为0，因为以自己为根节点
        }
    }

    public int find(int x) {
        if (root[x] == x) {
            return x;
        }
        return find(root[x]);
    }

    public void union(int x,int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            // 此时我们需要比较两个根节点之间的高度
            if (rank[rootX] < rank[rootY]) {
                // 如果rootX的高度小于rooY,将rootX的子树连接到rootY
                // 此时连接之后的树的高度不变
                root[rootX] = rootY;
            }
            else if (rank[rootX] > rank[rootY]) {
                root[rootY] = rootX;
            }
            else if (rank[rootX] == rank[rootY]) {
                root[rootY] = rootX;
                rank[rootY]++; // 树的高度+1
            }
        }
    }

    public static void main(String[] args) {
        UnionFind_weight unionFind = new UnionFind_weight(6);
        unionFind.union(1,2);
        unionFind.union(3,4);
        unionFind.union(1,4);
        System.out.println(unionFind.find(0));
        System.out.println(unionFind.find(1));
        System.out.println(unionFind.find(2));
        System.out.println(unionFind.find(3));
        System.out.println(unionFind.find(4));
    }
}
